'''
https://leetcode.cn/problems/permutations-ii/submissions/607727781/
'''

from typing import List


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        def process(i):
            if i == n:
                ans.append(nums[:])
            else:
                for j in range(i, n):
                    nums[i], nums[j] = nums[j], nums[i]
                    process(i + 1)
                    nums[i], nums[j] = nums[j], nums[i]
        process(0)
        return ans
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        def process(i):
            if i == n:
                ans.append(nums[:])
            else:
                s = set()
                for j in range(i, n):
                    if nums[j] not in s:
                        s.add(nums[j])
                        nums[i], nums[j] = nums[j], nums[i]
                        process(i + 1)
                        nums[i], nums[j] = nums[j], nums[i]
        process(0)
        return ans